#include "Tree.h"

ECOperateResult TreapTree::UpdateSize(int& Node)
{
	TreeItem[Node].Size = TreeItem[TreeItem[Node].LeftSon].Size + TreeItem[TreeItem[Node].RightSon].Size+ TreeItem[Node].cnt;
	return ECOperateResult::Success;
}

ECOperateResult TreapTree::LeftRotate(int& Root)
{
	int RightSon = TreeItem[Root].RightSon;
	TreeItem[Root].RightSon = TreeItem[RightSon].LeftSon; TreeItem[RightSon].LeftSon = Root; Root = RightSon;
	UpdateSize(TreeItem[Root].LeftSon);
	return ECOperateResult::Success;
}

ECOperateResult TreapTree::RightRotate(int& Node)
{
	int LeftSon = TreeItem[Root].LeftSon;
	TreeItem[Root].LeftSon = TreeItem[LeftSon].RightSon; TreeItem[LeftSon].RightSon = Root; Root = LeftSon;
	UpdateSize(TreeItem[Root].RightSon);
	return ECOperateResult::Success;
}

ECOperateResult TreapTree::Insert(int Value, int &Root)   //维护小根堆
{
	if (!Root)
	{
		Root = CreatNewNode(Value);
	}
	if (TreeItem[Root].Value >Value)
	{
		Insert(Value, TreeItem[Root].LeftSon);
		if (TreeItem[Root].Key < TreeItem[TreeItem[Root].LeftSon].Key) RightRotate(Root);
	}
	else if (TreeItem[Root].Value < Value)
	{
		Insert(Value, TreeItem[Root].RightSon);
		if (TreeItem[Root].Key < TreeItem[TreeItem[Root].RightSon].Key) LeftRotate(Root);
	}
	else TreeItem[Root].cnt++;
	UpdateSize(Root);
	return ECOperateResult::Success;
}

ECOperateResult TreapTree::Delete(int Value, int &Root)
{
	if (!Root) return ECOperateResult::Success;
	if (Value > TreeItem[Root].Value)
		Delete(Value, TreeItem[Root].RightSon);
	else if (Value < TreeItem[Root].Value)
		Delete(Value, TreeItem[Root].LeftSon);
	else
	{
		if (TreeItem[Root].cnt > 1) TreeItem[Root].cnt--; 
		else if (TreeItem[Root].LeftSon || TreeItem[Root].RightSon)
		{
			if (!TreeItem[Root].RightSon || (!TreeItem[Root].LeftSon && TreeItem[TreeItem[Root].LeftSon].Key > TreeItem[TreeItem[Root].RightSon].Key))
			{
				RightRotate(Root);
				Delete(Value, Root);
			}
			else
			{
				LeftRotate(Root);
				Delete(Value, Root);
			}
		}
		else Root = 0;
	}
	UpdateSize(Root);
	return ECOperateResult::Success;
}

int TreapTree::FindRank(int Value,int Root)
{
	if (!Root) return 0;
	if (Value > TreeItem[Root].Value)
		return FindRank(Value, TreeItem[Root].RightSon) + TreeItem[TreeItem[Root].LeftSon].Size+TreeItem[Root].cnt;
	else if (Value < TreeItem[Root].Value)
		return FindRank(Value, TreeItem[Root].LeftSon);
	else 
		return TreeItem[TreeItem[Root].LeftSon].Size + 1;
}

int TreapTree::CreatNewNode(int Value)
{
	TreeItem[++CurrentSize].Value = Value;
	TreeItem[CurrentSize].Key = std::rand();
	TreeItem[CurrentSize].cnt = TreeItem[CurrentSize].Size = 1;
	return CurrentSize;
}

int TreapTree::FindValue(int Rank, int Root)
{
	if (!Root) return std::numeric_limits<uint32_t>::max();
	if (TreeItem[TreeItem[Root].LeftSon].Size >= Rank)
		return FindValue(Rank, TreeItem[Root].LeftSon);
	else if (TreeItem[TreeItem[Root].LeftSon].Size+TreeItem[Root].cnt < Rank)
		return FindValue(Rank - TreeItem[TreeItem[Root].LeftSon].Size - TreeItem[Root].cnt, TreeItem[Root].RightSon);
	else return TreeItem[Root].Value;
}

int TreapTree::FindSuccessor(int Value, int Root)
{
	if (!Root) return 0x7ffffff;
	if (Value >= TreeItem[Root].Value)
		return FindSuccessor(Value, TreeItem[Root].RightSon); // 向左子树递归调用 UpperBound 函数
	return std::min(TreeItem[Root].Value, FindSuccessor(Value, TreeItem[Root].LeftSon)); // 返回 value 和递归结果中的一个较小值
}

int TreapTree::FindPredecessor(int Value, int Root)
{
	if (!Root) return std::numeric_limits<uint32_t>::max();
	if (Value <= TreeItem[Root].Value)
		return FindPredecessor(Value, TreeItem[Root].LeftSon); // 向右子树递归调用 LowerBound 函数
	return std::max(TreeItem[Root].Value, FindPredecessor(Value, TreeItem[Root].RightSon)); // 返回 value 和递归结果中的一个较小值
}

ECOperateResult TreapTree::Insert(int Value)
{
	return Insert(Value,Root);
}

ECOperateResult TreapTree::Delete(int Value)
{
	return Delete(Value,Root);
}

int TreapTree::FindRank(int Value)
{
	return FindRank(Value,Root);
}

int TreapTree::FindValue(int Rank)
{
	return FindValue(Rank,Root);
}

int TreapTree::FindSuccessor(int Node)
{
	return FindSuccessor(Node, Root);
}

int TreapTree::FindPredecessor(int Node)
{
	return  FindPredecessor(Node,Root);
}
